import java.util.Arrays;
import java.util.Random;

public class DirectInsertionSort {
    /*
    * 时间复杂度： O(N^2)
    * 空间复杂度：O(1)  只有 一个 tmp 变量是常驻的
    * 稳定性：稳定
    * */
    public static void insertionSort(int[] array){
        for(int i = 1;i < array.length;i++){
            int tmp = array[i];
            int j = i - 1;
            for( ; j >= 0;j-- ){
                if(tmp < array[j]){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    // 有序
    public static void test1(int capacity){
        int[] array = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        insertionSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
    // 无序
    public static void test2(int capacity){
        int[] array = new int[capacity];
        Random random = new Random();
        for (int i = 0; i < capacity; i++) {
            array[i] = random.nextInt(capacity);
        }
        long start = System.currentTimeMillis();
        insertionSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }


    public static void main(String[] args) {
        test1(10000);
        test2(10000);
    }
}
